package com.lzhsite.leetcode.algoritom.practise.dynamicProgramming;
/*
 给定两个字符串，求解这两个字符串的最长公共子序列（Longest Common Sequence）。
 比如字符串1：BDCABA；字符串2：ABCBDAB
则这两个字符串的最长公共子序列长度为4，最长公共子序列是：BCBA
*/

public class LCSubsequence {

	public static String lcse(String str1, String str2) {
		if (str1 == null || str2 == null || str1.equals("") || str2.equals("")) {
			return "";
		}
		char[] chs1 = str1.toCharArray();
		char[] chs2 = str2.toCharArray();
		int[][] dp = getdp(chs1, chs2);
		int m = chs1.length - 1;
		int n = chs2.length - 1;
		char[] res = new char[dp[m][n]];
		int index = res.length - 1;
		while (index >= 0) {
			if (n > 0 && dp[m][n] == dp[m][n - 1]) {
				n--;
			} else if (m > 0 && dp[m][n] == dp[m - 1][n]) {
				m--;
			} else {
				res[index--] = chs1[m];
				m--;
				n--;
			}
		}
		return String.valueOf(res);
	}

	public static int[][] getdp(char[] str1, char[] str2) {
		int[][] dp = new int[str1.length][str2.length];
		dp[0][0] = str1[0] == str2[0] ? 1 : 0;
		for (int m = 1; m < str1.length; m++) {
			dp[m][0] = Math.max(dp[m - 1][0], str1[m] == str2[0] ? 1 : 0);
		}
		for (int n = 1; n < str2.length; n++) {
			dp[0][n] = Math.max(dp[0][n - 1], str1[0] == str2[n] ? 1 : 0);
		}
		for (int m = 1; m < str1.length; m++) {
			for (int n = 1; n < str2.length; n++) {
				dp[m][n] = Math.max(dp[m - 1][n], dp[m][n - 1]);
				if (str1[m] == str2[n]) {
					dp[m][n] = Math.max(dp[m][n], dp[m - 1][n - 1] + 1);
				}
			}
		}
		return dp;
	}

	public static void main(String[] args) {
		String str1 = "A1BC2D3EFGH45I6JK7LMN";
		String str2 = "12OPQ3RST4U5V6W7XYZ";
		System.out.println(lcse(str1, str2));

	}
}